The present application relates to a decoding apparatus for executing a decoding process for an LDPC code.
In recent years, research has been and is being carried out remarkably, for example, in the field of communication including mobile communication and deep space communication and the field of broadcasting including ground wave broadcasting or satellite digital broadcasting. Together with the research, also research relating to a coding theory, is being carried out energetically in order to raise the efficiency in error correction coding and decoding.
As a theoretical limit to the code performance, the Shannon limit provided by the channel coding theory of Shannon (C. E. Shannon) is known. Research relating to the code theory is carried out in order to develop a code which exhibits a performance proximate to the Shannon limit. In recent years, as a coding method which exhibits a performance proximate to the Shannon limit, a technique called turbo codes such as, for example, parallel concatenated convolutional codes (PCCC) or serially concatenated convolutional codes (SCCC) has been developed. While such turbo codes are developed, attention is paid to low density parity check codes (hereinafter referred to as LDPC codes) which are a coding method known for long.
The LDPC codes were proposed first by R. G. Gallager, “Low density parity check codes,” Cambridge, Mass.: M. I. T. Press, 1963. After that, attention was paid again by D. J. C. MacKay, “Good error correction codes based on very sparse matrices,” IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999, M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, “Analysis of low density codes and improved designs using irregular graphs,” in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998, and so forth.
It is being discovered by research in recent years that, as the code length of the LDPC codes increases, a performance closer to the Shannon limit is obtained similarly with the turbo codes and so forth. Further, since the LDPC codes have a nature that the minimum distance increases in proportion to the code length, they have a characteristic that they exhibit a good probability property and is advantageous also in that an error floor phenomenon which is observed from a decoding characteristic of the turbo codes and so forth little occurs with the LDPC codes, as disclosed in R. G. Gallager, “Low density parity check codes,” IRE Trans. Inform. Theory, vol. 8, pp. 21-28, January, 1962 (hereinafter referred to as Non-Patent Document 1).
The LDPC codes are linear codes defined by a sparse parity check matrix H which includes a very small number of non-zero value elements, and those codes wherein the number of non-zero value elements is fixed among rows and columns of the check matrix H are called regular LDPC codes while those codes other than the codes described are called irregular LDPC codes.
Coding of LDPC codes is carried out in the following manner. In particular, Gaussian elimination and replacement of appropriate columns are applied to the check matrix H to generate a generation matrix G, and a vector c of a codeword of n bits is generated based on a vector s of k information bits and the generation matrix G. Further details of the coding are disclosed in D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol. 45, pp. 399-431, October 1999 (hereinafter referred to as Non-Patent Document 2).
As a representative decoding method for LDPC codes, a sum-product decoding method is available. The sum-product decoding method is basically equivalent to an algorithm known as Belief Propagation (BP).
Further, the LDPC codes are decoded by an iterative decoding algorithm based on a message passing algorithm which operates on a Tanner graph which defines the LDPC codes.
On the Tanner graph, each variable node corresponds to a column of the check matrix H, and each check node corresponds to a row of the check matrix H. Further, while the target of the algorithm is to determine a posteriori probability corresponding to each transmission symbol from received values, since generally a Tanner graph of the LDPC codes includes a loop, an accurate posteriori probability cannot be calculated by the BP, but approximate calculation is used. However, it is known that, where the graphs are sparse, the approximation technique provides a comparatively good result.
Also an algorithm (Layered BP algorithm) has been proposed wherein, by updating, for every row of the check matrix, a message P from a variable node to a check node which is used for updating of a message a from the check node to the variable node in the sum-product decoding method, even if the number of times of iteration is small, a performance similar to that of an ordinary sum-product decoding method can be implemented and also the memory amount can be reduced. The Layered BP algorithm is disclosed, for example, in D. E. Hocevar, “A reduced complexity decoder architecture via layered decoding of LDPC codes,” IEEE Workshop on Signal Processing Systems, pp. 107-112, 2004 hereinafter referred to as Non-Patent Document 3).
In such LDPC decoding, it is necessary to select, from within a logarithmic likelihood vector ?=[λ1 λ2 . . . λn . . . λN] or a logarithmic posteriori probability ratio vector Q=[q1 q2 . . . qn . . . qN] for one codeword, where the element in the mth row of the nth column of the check matrix H of M roses and N columns is represented by hmn, those elements which satisfy hmn=1 for each row of the check matrix H. For example, if it is assumed that hmn=1 is satisfied by NH sets and the time interval is represented by TS, time of 2×NH×TS is necessary in order to carry out updating of a message from a variable node to a check node and to carry out updating of a message from a check node to variable node regarding each set. Further, if the updating of a message from a variable node to a check node and the updating of a message from a check node to a variable node are carried out repetitively by NI times, then the time required to decode a reception codeword is 2×NH×NI×TS. Usually, the latency permitted for decoding is in most cases lower than 2×NH×NI×TS, and it is somewhat difficult to incorporate this configuration.
Therefore, a sum-product decoding method wherein calculation for message updating is carried out simultaneously at all nodes has been proposed and is disclosed, for example, in C. Howvland and A. Blanksby, “Parallel Decoding Architectures for Low Density Parity Check Codes,” IEEE International Symposium on Circuits and Systems, vol. 4, pp. 742-745, May. 2001 (hereinafter referred to as Non-Patent Document 4). In the configuration of the sum-product decoding method, since calculation for NH sets is carried out in one clock, the time required for decoding is 2×NI×TS, and therefore, the latency can be reduced significantly.
Also a configuration has been proposed wherein row replacement or column replacement is carried out for a check matrix to convert the check matrix into another check matrix which can be represented by a combination of component matrices such as P×P unit matrices, quasi-unit matrices wherein one or more 1s among components of the unit matrix are changed into 0, a shift matrix obtained by cyclically shifting the unit matrix or quasi-unit matrix, a sum matrix which is the sum of a plurality of ones of unit matrices, quasi-with matrices and shift matrices or a P×P zero matrix. By the configuration, it is possible to carry out updating of a message from a check node to a variable node in decoding of LDPC codes and carry out calculation for updating of a message from a variable node into a check node parallelly for P messages. The configuration described is disclosed, for example, in Japanese Patent Laid-Open No. 2004-343170 (hereinafter referred to as Patent Document 1). With the configuration, it is possible to suppress the circuit scale within a range within which it can be implemented while the number of clocks to be used for decoding is suppressed. In the case of the configuration, the time required for decoding is 2×NH×NI×TS/P. Where a check matrix is represented by such a combination of component matrices as described above, a matrix of M/P rows and N/P columns wherein each component matrix which is a zero matrix is replaced by 0 and each component matrix which is not a zero matrix is replaced by 1 is called weight matrix.
However, the technique of the Non-Patent Document 4 has a problem in that an increased circuit scale is necessary because it is necessary to carry out calculation for message updating at all nodes parallelly. Further, according to the technique, since connection between nodes is established by wiring lines, there is a problem that it is difficult to share a decoder among a plurality of check matrices.
Further, in the case of the Layered BP decoding method, a configuration may be used wherein a plurality of logarithmic posteriori probability ratios qn which satisfy, hmn=1 in each row of a check matrix are read out at a time and calculation for message updating for one row of the check matrix is carried out in parallel. However, in order to implement this configuration, a selector is necessary which stores logarithmic posteriori probability ratios qn into registers and select a plurality of logarithmic posteriori probability ratios qn which satisfy hmn=1 in each row, for example, from a number of logarithmic posteriori probability ratios qn equal to the code length, that is, equal to N. Generally, since the code length of LDPC codes is as great as several thousands to several tens thousands, it is estimated that the configuration needs an increased circuit scale.
Further, depending upon an application to be incorporated in a case wherein it is used for a next generation radio LAN or the like, the required latency is so severe that it may not be satisfied even by the configuration of Patent Document 1.